(0) Obligation:
The Runtime Complexity (innermost) of the given
CpxTRS could be proven to be
BOUNDS(1, n^1).
The TRS R consists of the following rules:
concat(leaf, Y) → Y
concat(cons(U, V), Y) → cons(U, concat(V, Y))
lessleaves(X, leaf) → false
lessleaves(leaf, cons(W, Z)) → true
lessleaves(cons(U, V), cons(W, Z)) → lessleaves(concat(U, V), concat(W, Z))
Rewrite Strategy: INNERMOST
(1) CpxTrsMatchBoundsTAProof (EQUIVALENT transformation)
A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2.
The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by:
final states : [1, 2]
transitions:
leaf0() → 0
cons0(0, 0) → 0
false0() → 0
true0() → 0
concat0(0, 0) → 1
lessleaves0(0, 0) → 2
concat1(0, 0) → 3
cons1(0, 3) → 1
false1() → 2
true1() → 2
concat1(0, 0) → 4
concat1(0, 0) → 5
lessleaves1(4, 5) → 2
cons1(0, 3) → 3
cons1(0, 3) → 4
cons1(0, 3) → 5
concat1(0, 3) → 5
concat1(0, 3) → 4
concat2(0, 3) → 6
concat2(0, 3) → 7
lessleaves2(6, 7) → 2
concat1(0, 3) → 3
0 → 1
0 → 3
0 → 4
0 → 5
3 → 4
3 → 5
3 → 6
3 → 7
(2) BOUNDS(1, n^1)